package com.lfg.leetcode.leetcode0;

import java.util.Stack;

public class No84largestRectangleArea2 {

    public static void main(String[] args) {
        int ret = largestRectangleArea(new int[]{15, 6, 8, 1, 2, 3, 1, 0, 11});
        System.out.println(ret);
    }

    public static int largestRectangleArea(int[] heights) {
        int[] left = new int[heights.length];
        int[] right = new int[heights.length];

        Stack<Integer> stack = new Stack<>();


        for (int i = 0; i < heights.length; i++) {
            while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) {
                stack.pop();
            }
            if (stack.isEmpty()) {
                left[i] = -1;
            } else {
                left[i] = stack.peek();
            }
            stack.push(i);
        }
        stack.clear();
        for (int r = heights.length - 1; r >= 0; r--) {
            while (!stack.isEmpty() && heights[stack.peek()] > heights[r]) {
                stack.pop();
            }
            if (stack.isEmpty()) {
                right[r] = heights.length ;
            } else {
                right[r] = stack.peek();
            }
            stack.push(r);
        }
        int ret = 0;
        for (int i = 0; i < heights.length; i++) {
            ret = Math.max(ret, heights[i] * (right[i] - left[i]-1));
        }

        return ret;
    }


}

